#include "common.h"
//

// 76. Minimum Window Substring

class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> char_nr_in_t;
        unordered_map<char, int> char_nr_in_s;

        for (auto &ch : t)
        {
            ++char_nr_in_t[ch];
        }
        int tsize = t.size();
        int ssize = s.size();
        int left = 0, right = 0;
        int count = 0;
        int sz = INT_MAX;
        int begin = -1;
        while (right < ssize)
        {
            // when s[right] is valid char count auto_increment by 1
            if (++char_nr_in_s[s[right]] <= char_nr_in_t[s[right]])
            {
                count++;
            }
            // insert new char make count incresed by 1
            // so let's check the validation of 'count'
            // check count: if 'count' is smaller than self change it
            while (count == tsize)
            {
                if (right - left + 1 < sz)
                {
                    begin = left;
                    sz = right - left + 1;
                }
                if (char_nr_in_s[s[left]]-- <= char_nr_in_t[s[left]])
                {
                    count--;
                }
                left++;
            }
            right++;
        }
        return begin >= 0 ? s.substr(begin,sz) : "";
    }
};


//Optimization
class Solution
{
    public:
    string minWindow(string s, string t)
    {
        int hash1[128] = {0};
        int hash2[128] = {0};
        for(auto & ch : t)
        {
            ++hash1[ch];
        }
        int left = 0, right = 0, count = 0/*char valid*/, begin = 0, min_len = INT_MAX;

        while(right < s.size())
        {
            if(++hash2[s[right]] <= hash1[s[right]]) count++;

            while(count == t.size())
            {
                if(right - left + 1 < min_len)
                {
                    min_len = right - left + 1;
                    begin = left;
                }
                if(hash2[s[left]]-- <= hash1[s[left]]) count--;
                left++;
            }
            right++;
        }
        return min_len == INT_MAX ? "" : s.substr(begin, min_len);
    }
};